{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 对所有可能的匹配m属于M'，计算CH(m)可能取得的最大值"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "# This Python 3 environment comes with many helpful analytics libraries installed\n",
    "# It is defined by the kaggle/python docker image: https://github.com/kaggle/docker-python\n",
    "# For example, here's several helpful packages to load in \n",
    "\n",
    "import numpy as np # linear algebra\n",
    "import pandas as pd # data processing, CSV file I/O (e.g. pd.read_csv)\n",
    "import math\n",
    "from collections import Counter\n",
    "\n",
    "# Input data files are available in the \"../input/\" directory.\n",
    "# For example, running this (by clicking run or pressing Shift+Enter) will list the files in the input directory\n",
    "\n",
    "from subprocess import check_output\n",
    "# print(check_output([\"ls\", \"../input\"]).decode(\"utf8\"))\n",
    "\n",
    "n_children = 1000000 # n children to give\n",
    "n_gift_type = 1000 # n types of gifts available\n",
    "n_gift_quantity = 1000 # each type of gifts are limited to this quantity\n",
    "n_gift_pref = 100 # number of gifts a child ranks\n",
    "n_child_pref = 1000 # number of children a gift ranks\n",
    "twins = math.ceil(0.04 * n_children / 2.) * 2    # 4% of all population, rounded to the closest number\n",
    "triplets = math.ceil(0.005 * n_children / 3.) * 3    # 0.5% of all population, rounded to the closest number\n",
    "ratio_gift_happiness = 2\n",
    "ratio_child_happiness = 2\n",
    "\n",
    "gift_pref = pd.read_csv('../input/child_wishlist_v2.csv',header=None).drop(0, 1).values\n",
    "child_pref = pd.read_csv('../input/gift_goodkids_v2.csv',header=None).drop(0, 1).values"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "((1000000, 100), (1000, 1000))"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "gift_pref.shape, child_pref.shape"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Child(object):\n",
    "    \n",
    "    def __init__(self, idx, prefer):\n",
    "        # 每个孩子有自己的ID和prefer列表，这里使用字典来存储prefer列表中的giftID和对应的happiness，\n",
    "        # 这里的happiness使用包含两个值的列表存储，前者是礼物为此giftID的happiness，后者是礼物不在prefer列表的happiness\n",
    "        self.idx = idx\n",
    "        self.prefer_dict = dict()\n",
    "        for i in range(prefer.shape[0]):\n",
    "            self.prefer_dict[prefer[i]] = [12*(prefer.shape[0] - i), -6]\n",
    "    \n",
    "    def add_gifts_prefer(self, giftid, score):\n",
    "        # 添加gift对child的prefer，前者为孩子对礼物的happiness，后者对礼物对孩子的happiness\n",
    "        if giftid in self.prefer_dict.keys():\n",
    "            self.prefer_dict[giftid][1] = 6*score\n",
    "        else:\n",
    "            self.prefer_dict[giftid] = [-6, 6*score]\n",
    "        return None\n",
    "        \n",
    "    def happiness(self, giftid):\n",
    "        # 获取当前childID和指定giftID的happiness对\n",
    "        # 若giftID不在prefer字典中，则返回[-6,-6]\n",
    "        return self.prefer_dict.get(giftid, [-6, -6])\n",
    "    \n",
    "class Child_twin(object):\n",
    "    \n",
    "    def __init__(self, idx, prefer1, prefer2):\n",
    "        \n",
    "        self.idx = idx\n",
    "        self.prefer_dict = dict()\n",
    "        # 构造twins的prefer字典，用giftID在两个prefer列表中的score之和的三倍（平均score的6倍）和-6作为value\n",
    "        for p in list(set(list(prefer1) + list(prefer2))):\n",
    "            score = 0\n",
    "            if p in list(prefer1):\n",
    "                score += 2*(100 - list(prefer1).index(p))\n",
    "            else:\n",
    "                score -= 1\n",
    "            if p in list(prefer2):\n",
    "                score += 2*(100 - list(prefer2).index(p))\n",
    "            else:\n",
    "                score -= 1\n",
    "            self.prefer_dict[p] = [3*score, -6]\n",
    "    \n",
    "    \n",
    "    def add_gifts_prefer(self, giftid, score):\n",
    "        \n",
    "        if giftid in self.prefer_dict.keys():\n",
    "            self.prefer_dict[giftid][1] = 3*score\n",
    "        else:\n",
    "            self.prefer_dict[giftid] = [-6, 3*score] \n",
    "        return None\n",
    "        \n",
    "    \n",
    "    def happiness(self, giftid):  \n",
    "        return self.prefer_dict.get(giftid, [-6, -6])\n",
    "    \n",
    "class Child_triplet(object):\n",
    "    \n",
    "    def __init__(self, idx, prefer1, prefer2, prefer3):\n",
    "        \n",
    "        self.idx = idx\n",
    "        self.prefer_dict = dict()\n",
    "        \n",
    "        for p in list(set(list(prefer1) + list(prefer2) + list(prefer3))):\n",
    "            score = 0\n",
    "            if p in list(prefer1):\n",
    "                score += 2*(100 - list(prefer1).index(p))\n",
    "            else:\n",
    "                score -= 1\n",
    "            if p in list(prefer2):\n",
    "                score += 2*(100 - list(prefer2).index(p))\n",
    "            else:\n",
    "                score -= 1\n",
    "            if p in list(prefer3):\n",
    "                score += 2*(100 - list(prefer3).index(p))\n",
    "            else:\n",
    "                score -= 1\n",
    "            self.prefer_dict[p] = [2*score, -6]\n",
    "    \n",
    "    \n",
    "    def add_gifts_prefer(self, giftid, score):\n",
    "        \n",
    "        if giftid in self.prefer_dict.keys():\n",
    "            self.prefer_dict[giftid][1] = 2*score\n",
    "        else:\n",
    "            self.prefer_dict[giftid] = [-6, 2*score]\n",
    "        \n",
    "        return None\n",
    "        \n",
    "    \n",
    "    def happiness(self, giftid):\n",
    "        return self.prefer_dict.get(giftid, [-6, -6])\n",
    "    \n",
    "# 构造childID的prefer字典\n",
    "Children = []\n",
    "for i in range(0, 5001, 3):\n",
    "    Children.append(Child_triplet(i, gift_pref[i], gift_pref[i+1], gift_pref[i+2]))\n",
    "    Children.append(Child_triplet(i+1, gift_pref[i], gift_pref[i+1], gift_pref[i+2]))\n",
    "    Children.append(Child_triplet(i+2, gift_pref[i], gift_pref[i+1], gift_pref[i+2]))\n",
    "for i in range(5001, 45001, 2):\n",
    "    Children.append(Child_twin(i, gift_pref[i], gift_pref[i+1]))\n",
    "    Children.append(Child_twin(i+1, gift_pref[i], gift_pref[i+1]))\n",
    "Children = Children + [Child(i, gift_pref[i]) for i in range(45001, 1000000)]\n",
    "\n",
    "# 构造giftID的prefer字典\n",
    "for j in range(1000):# 遍历所有的giftID\n",
    "    cf = child_pref[j]\n",
    "    done_list = []\n",
    "    for i in range(cf.shape[0]):# 遍历一个giftID下所有的preferred kid ID\n",
    "        # 如果是三胞胎中的一个，而且没有被处理，就一次性处理三胞胎\n",
    "        if cf[i] <= 5000 and cf[i] not in done_list:\n",
    "            if cf[i] % 3 == 0:\n",
    "                cid1 = cf[i]\n",
    "                cid2 = cf[i] + 1\n",
    "                cid3 = cf[i] + 2\n",
    "                done_list.append(cid2)\n",
    "                done_list.append(cid3)\n",
    "            elif cf[i] % 3 == 1:\n",
    "                cid1 = cf[i] - 1\n",
    "                cid2 = cf[i]\n",
    "                cid3 = cf[i] + 1\n",
    "                done_list.append(cid1)\n",
    "                done_list.append(cid3)\n",
    "            else:\n",
    "                cid1 = cf[i] - 2\n",
    "                cid2 = cf[i] - 1\n",
    "                cid3 = cf[i]\n",
    "                done_list.append(cid1)\n",
    "                done_list.append(cid2)\n",
    "            if cid1 in list(cf):\n",
    "                score_ = 2*(cf.shape[0] - list(cf).index(cid1))\n",
    "            else:\n",
    "                score_ = -1\n",
    "            if cid2 in list(cf):\n",
    "                score_ += 2*(cf.shape[0] - list(cf).index(cid2))\n",
    "            else:\n",
    "                score_ += -1\n",
    "            if cid3 in list(cf):\n",
    "                score_ += 2*(cf.shape[0] - list(cf).index(cid3))\n",
    "            else:\n",
    "                score_ += -1\n",
    "            Children[cid1].add_gifts_prefer(j, score_)\n",
    "            Children[cid2].add_gifts_prefer(j, score_)\n",
    "            Children[cid3].add_gifts_prefer(j, score_)\n",
    "        # 如果是twins中的childID，而且没有被处理，就一次性处理twins\n",
    "        elif cf[i] <= 45000 and cf[i] not in done_list:\n",
    "            if cf[i] % 2 == 1:\n",
    "                cid1 = cf[i]\n",
    "                cid2 = cf[i] + 1\n",
    "                done_list.append(cid2)\n",
    "            else:\n",
    "                cid1 = cf[i] - 1\n",
    "                cid2 = cf[i]\n",
    "                done_list.append(cid1)\n",
    "            if cid1 in list(cf):\n",
    "                score_ = 2*(cf.shape[0] - list(cf).index(cid1))\n",
    "            else:\n",
    "                score_ = -1\n",
    "            if cid2 in list(cf):\n",
    "                score_ += 2*(cf.shape[0] - list(cf).index(cid2))\n",
    "            else:\n",
    "                score_ += -1\n",
    "            Children[cid1].add_gifts_prefer(j, score_)\n",
    "            Children[cid2].add_gifts_prefer(j, score_)\n",
    "        elif cf[i] > 45000:\n",
    "            Children[cf[i]].add_gifts_prefer(j, 2*(cf.shape[0] - i))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "from ortools.graph import pywrapgraph\n",
    "\n",
    "W_CHILD = 1\n",
    "W_GIFTS = 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "101550693"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "min_cost_flow = pywrapgraph.SimpleMinCostFlow()\n",
    "\n",
    "start_nodes = []\n",
    "end_nodes = []\n",
    "capacities = []\n",
    "unit_costs = []\n",
    "\n",
    "# triplets\n",
    "for i in range(0, 5001, 3):\n",
    "    for g in Children[i].prefer_dict.keys():\n",
    "        start_nodes.append(1000000+g)\n",
    "        end_nodes.append(i)\n",
    "        capacities.append(3)\n",
    "        unit_costs.append(1-W_CHILD*(Children[i].prefer_dict[g][0] + 6)-W_GIFTS*(Children[i].prefer_dict[g][1] + 6))\n",
    "            \n",
    "# twins\n",
    "for i in range(5001, 45001, 2):\n",
    "    for g in Children[i].prefer_dict.keys():\n",
    "        start_nodes.append(1000000+g)\n",
    "        end_nodes.append(i)\n",
    "        capacities.append(2)\n",
    "        unit_costs.append(1-W_CHILD*(Children[i].prefer_dict[g][0] + 6)-W_GIFTS*(Children[i].prefer_dict[g][1] + 6))\n",
    "        \n",
    "# other children\n",
    "for i in range(45001, 1000000):\n",
    "    \n",
    "    for g in Children[i].prefer_dict.keys():\n",
    "        start_nodes.append(1000000+g)\n",
    "        end_nodes.append(i)\n",
    "        capacities.append(1)\n",
    "        unit_costs.append(-W_CHILD*(Children[i].prefer_dict[g][0] + 6)-W_GIFTS*(Children[i].prefer_dict[g][1] + 6))\n",
    "\n",
    "# add Arc\n",
    "# gift -> children\n",
    "for i in range(len(start_nodes)):\n",
    "    min_cost_flow.AddArcWithCapacityAndUnitCost(\n",
    "        int(start_nodes[i]), int(end_nodes[i]), int(capacities[i]), int(unit_costs[i])\n",
    "    )\n",
    "    \n",
    "# children -> 1001000 : collection\n",
    "for i in range(0, 5001, 3):\n",
    "    min_cost_flow.AddArcWithCapacityAndUnitCost(\n",
    "        int(i), int(1001000), int(3), int(0)\n",
    "    )\n",
    "for i in range(5001, 45001, 2):\n",
    "    min_cost_flow.AddArcWithCapacityAndUnitCost(\n",
    "        int(i), int(1001000), int(2), int(0)\n",
    "    )\n",
    "for i in range(45001, 1000000):\n",
    "    min_cost_flow.AddArcWithCapacityAndUnitCost(\n",
    "        int(i), int(1001000), int(1), int(0)\n",
    "    )\n",
    "    \n",
    "# gift -> 1001001 : dust_gift\n",
    "for i in range(1000):\n",
    "    min_cost_flow.AddArcWithCapacityAndUnitCost(\n",
    "        int(1000000+i), int(1001001), int(1000), int(0)\n",
    "    )\n",
    "    \n",
    "# 1001001 -> 1001000 : dust_path\n",
    "min_cost_flow.AddArcWithCapacityAndUnitCost(\n",
    "    int(1001001), int(1001000), int(1000000), int(0)\n",
    ")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# add Supply\n",
    "for i in range(1000):\n",
    "    min_cost_flow.SetNodeSupply(int(1000000+i), int(1000))\n",
    "\n",
    "# children\n",
    "for i in range(0, 5001, 3):\n",
    "    min_cost_flow.SetNodeSupply(int(i), int(0))\n",
    "for i in range(5001, 45001, 2):\n",
    "    min_cost_flow.SetNodeSupply(int(i), int(0))\n",
    "for i in range(45001, 1000000):\n",
    "    min_cost_flow.SetNodeSupply(int(i), int(0))\n",
    "\n",
    "min_cost_flow.SetNodeSupply(int(1001001), int(0)) \n",
    "min_cost_flow.SetNodeSupply(int(1001000), int(-1000000)) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "min_cost_flow.Solve()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1 0 11739596260 44598 1617929090195333159939167951192\n",
      "0.936301556826003\n"
     ]
    }
   ],
   "source": [
    "assignment = [-1]*1000000\n",
    "twins_differ = []\n",
    "triplets_differ = []\n",
    "\n",
    "#for i in well_assigned:\n",
    "#    assignment[i] = assignment_0[i]\n",
    "\n",
    "for i in range(min_cost_flow.NumArcs()):\n",
    "    if min_cost_flow.Flow(i) != 0 and min_cost_flow.Head(i) < 1000000:\n",
    "        c = min_cost_flow.Head(i)\n",
    "        g = min_cost_flow.Tail(i)\n",
    "        f = min_cost_flow.Flow(i)\n",
    "\n",
    "        if c >= 45001:\n",
    "            assignment[c] = g - 1000000\n",
    "\n",
    "        elif c >= 5001:\n",
    "            if f == 1:\n",
    "                if assignment[c] == -1:\n",
    "                    assignment[c] = g - 1000000\n",
    "                    twins_differ.append([c, c+1])\n",
    "                else:\n",
    "                    assignment[c+1] = g - 1000000\n",
    "            elif f == 2:\n",
    "                assignment[c] = g - 1000000\n",
    "                assignment[c+1] = g - 1000000\n",
    "        else:\n",
    "            if f == 1:\n",
    "                if assignment[c] == -1:\n",
    "                    assignment[c] = g - 1000000\n",
    "                    triplets_differ.append([c, c+1, c+2])\n",
    "                elif assignment[c+1] == -1:\n",
    "                    assignment[c+1] = g - 1000000\n",
    "                else:\n",
    "                    assignment[c+2] = g - 1000000\n",
    "            elif f == 2:\n",
    "                if assignment[c] == -1:\n",
    "                    assignment[c] = g - 1000000\n",
    "                    assignment[c+1] = g - 1000000\n",
    "                    triplets_differ.append([c, c+1, c+2])\n",
    "                else:\n",
    "                    assignment[c+1] = g - 1000000\n",
    "                    assignment[c+2] = g - 1000000\n",
    "            elif f == 3:\n",
    "                assignment[c] = g - 1000000\n",
    "                assignment[c+1] = g - 1000000\n",
    "                assignment[c+2] = g - 1000000\n",
    "                \n",
    "CHILD_HAPPINESS = sum([Children[i].happiness(assignment[i])[0] for i in range(1000000)])*10\n",
    "SANTA_HAPPINESS = sum([Children[i].happiness(assignment[i])[1] for i in range(1000000)])\n",
    "OBJ = CHILD_HAPPINESS**3 + SANTA_HAPPINESS**3\n",
    "print(W_CHILD, W_GIFTS, CHILD_HAPPINESS, SANTA_HAPPINESS, OBJ)\n",
    "print(OBJ / (12000000000**3))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "anaconda-cloud": {},
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}
